package medium.number;

/**
 * <a href="https://leetcode-cn.com/problems/sum-of-square-numbers">633. 平方数之和</a>
 * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
 * 示例 1：
 *   输入：c = 5
 *   输出：true
 *   解释：1 * 1 + 2 * 2 = 5
 * 示例 2：
 *   输入：c = 3
 *   输出：false
 * 示例 3：
 *   输入：c = 4
 *   输出：true
 * 示例 4：
 *   输入：c = 2
 *   输出：true
 * 示例 5：
 *   输入：c = 1
 *   输出：true
 * 提示：
 *   0 <= c <= 2<sup>31</sup> - 1
 * 解题思路：
 *   1.定义两个数，一个数从0开始，另一个数从√c开始，分别表示a和b
 *   2.对a和b分别平方再求和，若结果等于c，直接返回true；若结果大于c，则b-1；若结果小于c，则a+1；
 *   3.循环步骤2，直到a>b，表示0~√c范围内没有符合a<sup>2</sup>+b<sup>2</sup>=c的数，返回false
 * @author 刘学松
 * @date 2021-04-13 16:40
 */
public class 平方数之和 {
    public static void main(String[] args) {

    }
    public static boolean judgeSquareSum(int c) {
        int left = 0;
        int right = (int) Math.sqrt(c);

        while (left <= right) {
            int sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum > c) {
                --right;
            } else {
                ++left;
            }
        }

        return false;
    }
}
